class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = []


class Solution:
    """这个方法有问题,可能有多个点连一个点,也可能有一个点连多个点"""
    def canFinish(self, numCourses: int, prerequisites: list) -> bool:
        class_list = [ListNode(i) for i in range(numCourses)]
        self.mid_set, self.flag = set(), True
        for lists in prerequisites:
            self.mid_set.update(lists)
            class_list[lists[0]].next.append(class_list[lists[1]])
        while self.mid_set:
            i = self.mid_set.pop()
            now_note1, now_note2 = class_list[i].next, class_list[i].next
            while now_note1 and now_note2 and now_note2.next:
                pass
        return self.flag

    def search(self, now_note1, now_note2):
        try:
            self.mid_set.remove(now_note2.val)
            self.mid_set.remove(now_note2.next.val)
        except:
            pass
        now_note1 = now_note1.next
        now_note2 = now_note2.next.next
        if now_note1 is now_note2:
            self.flag = False


class Solution2:
    def canFinish(self, numCourses: int, prerequisites: list) -> bool:
        mid_list = [[0, []] for i in range(numCourses)]
        for lists in prerequisites:
            mid_list[lists[0]][0] += 1
            mid_list[lists[1]][1].append(lists[0])
        # mid_res, search_list = 0, []
        # for lists in mid_list:
        #     if lists[0] == 0:
        #         search_list.append(lists)
        mid_res, search_list = 0, [mid_list[i] for i in range(numCourses) if mid_list[i][0] == 0]
        while search_list:
            # lists = search_list.pop(-1)  # 貌似下面那个快一点
            lists = search_list.pop(0)
            mid_res += 1
            for num in lists[1]:
                mid_list[num][0] -= 1
                if mid_list[num][0] == 0:
                    search_list.append(mid_list[num])
        return mid_res == numCourses


a = Solution2()
print(a.canFinish(2, [[1, 0], [0, 1]]))
print(a.canFinish(3, [[1, 0], [2, 1]]))
